[Coding001] LeetCode 1

Two Sum

More coding records

Get the knowledge flowing and circulating! :)

目录

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

xxxxxxxxxx
3
1
Input: nums = [2,7,11,15], target = 9
2
Output: [0,1]
3
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

xxxxxxxxxx
2
1
Input: nums = [3,2,4], target = 6
2
Output: [1,2]

Example 3:

xxxxxxxxxx
2
1
Input: nums = [3,3], target = 6
2
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2)time complexity?

解题

解法1

xxxxxxxxxx
14
1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        int i, j;
4
        for(i = 0; i < nums.length; i++)
5
        {
6
            for(j = i + 1; j < nums.length; j++)
7
            {
8
                if(target - nums[i] == nums[j])
9
                    return new int[]{i, j};  // 这里直接return一个数组
10
            }
11
        }
12
        return new int[]{0, 0}; // 这里直接return null就行了，更科学！
13
    }
14
}

解法1的时间复杂度分析

外层循环 0~n-1

内层循环最坏的情况下n-1次

所以时间复杂度是$O(n^2)$$O(n^2)$

解法2

xxxxxxxxxx
28
1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        // 要点注意
4
        // new后面跟的是HashMap
5
        // Map内的类型为Integer
6
        Map<Integer, Integer> map = new HashMap<>(); 
7

8
        for (int i = 0; i < nums.length; i++)
9
        {
10
            // 这里的值类型是Integer
11
            // get方法，获取键对应的值（这里的键是：value, 值是index）
12
            // 意思是，map中放的是(某数值，target-某数值对应的数值的index)
13
            Integer val = map.get(nums[i]); 
14
            if(val != null)
15
            {
16
                // 如果能查到，就返回下标
17
                return new int[]{i, val};
18
            }
19
            else
20
            {
21
                // 如果查不到，就在map中放入新的键值对（value, index）
22
                map.put(target-nums[i], i);
23
            }
24
        }
25

26
        return null;
27
    }
28
}

解法2的时间复杂度分析

全程一个for循环，能查到，就结束；查不到，就进行线性操作。

时间复杂度：$O(n)$$O(n)$

解题过程分析

设想target是目标，target由数组中的两个数相加得到。 数1 和 数2 暂且称为互补的数。 答案要的是这两个数的索引值（即数组中的下标）。

• 【情况1】使用HashMap，键存放数1，值存放数2的索引。遍历到数1的时候，由i标识，此时返回i和数2的索引（键为数1时对应的值）即构成答案。

• 【情况2】HashMap如果找到的键对应的值为null，说明两种可能：①这个值没有互补的数，②这个值的互补数还没加入HashMap. 这两种情况可以统一处理。即，将该值的互补数计算出来，然后按照【情况1】进行操作。

★ 知识点积累 (Java)

1. 一维数组的初始化

   xxxxxxxxxx
   4
   1
   // 一维数组的初始化
   2
   int[] solution = new int[2];
   3
   
   4
   int[] nums1 = new int[]{2, 7, 11, 15};
   

2. 直接返回一个数组的方法

   xxxxxxxxxx
   1
   1
   return new int[]{i, j};  // 这里直接return一个数组
   

3. map的用法

   xxxxxxxxxx
   7
   1
   Map<Integer, Integer> map = new HashMap<>(); 
   2
   map.put(key, value);
   3
   Integer value = map.get(key);
   4
   
   5
   Map<Integer, Integer> map = new HashMap<>();
   6
   Integer  val = map.get(nums[i]);  // value = map.get(key)
   7
   map.put(target - nums[i], i); // map.put(key, value)
   

   为什么要用HashMap?

   HashMap：基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

附（完整程序）

xxxxxxxxxx
47
1
package LeetCode;
2

3
import java.util.HashMap;
4
import java.util.Map;
5

6
class Solution
7
{
8
    public int[] twoSum(int[] nums, int target)
9
    {
10
        Map<Integer, Integer> map = new HashMap<>();
11

12
        for(int i = 0; i < nums.length; i++)
13
        {
14
            Integer  val = map.get(nums[i]);  // value = map.get(key)
15
            if(val != null)
16
            {
17
                return new int[]{val, i};
18
            }
19
            else
20
            {
21
                // {2,7,11,15};
22
                map.put(target - nums[i], i); // map.put(key, value)
23
                // {9-2, 0} 意思是，7这个数字如果作为key出现了，它所匹配的值就是配对为target的值的索引。
24
            }
25
        }
26
        return null;
27
    }
28
}
29
public class LeetCode0001 {
30
    public static void main(String[] args) {
31
        // TODO code application logic here
32
        int[] nums1 = new int[]{2, 7, 11, 15};
33
        int target1 = 9;
34

35
        int[] nums2 = new int[]{3, 2, 4};
36
        int target2 = 6;
37

38
        int[] nums3 = new int[]{3, 3};
39
        int target3 = 6;
40

41
        Solution sol = new Solution();
42
        int[] result =  sol.twoSum(nums3, target3);
43

44
        System.out.println(result[0] + " " + result[1]);
45
    }
46

47
}